package com.tried.kind.algorithm.sort;

import java.util.Arrays;

/**
 * 归并排序
 */
public class MergingSort {


    /**
     * 归并排序（Merging Sort）
     * 1、基本思想
     * 归并排序算法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。
     * 然后再把有序子序列合并为整体有序序列。
     * 2、算法描述
     * 归并排序可通过两种方式实现：
     *
     * 自上而下的递归
     * 自下而上的迭代
     * 一、递归法（假设序列共有n个元素）：
     *
     * ①. 将序列每相邻两个数字进行归并操作，形成 floor(n/2)个序列，排序后每个序列包含两个元素；
     * ②. 将上述序列再次归并，形成 floor(n/4)个序列，每个序列包含四个元素；
     * ③. 重复步骤②，直到所有元素排序完毕。
     *
     *
     *
     * 二、迭代法
     *
     * ①. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
     * ②. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
     * ③. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
     * ④. 重复步骤③直到某一指针到达序列尾
     * ⑤. 将另一序列剩下的所有元素直接复制到合并序列尾
     *
     * 3、代码实现
     * 归并排序其实要做两件事：
     *
     * 分解：将序列每次折半拆分
     * 合并：将划分后的序列段两两排序合并
     * 因此，归并排序实际上就是两个操作，拆分+合并
     *
     * 如何合并？
     *
     * L[first...mid]为第一段，L[mid+1...last]为第二段，并且两端已经有序，现在我们要将两端合成达到L[first...last]并且也有序。
     *
     * 首先依次从第一段与第二段中取出元素比较，将较小的元素赋值给temp[]
     * 重复执行上一步，当某一段赋值结束，则将另一段剩下的元素赋值给temp[]
     * 此时将temp[]中的元素复制给L[]，则得到的L[first...last]有序
     *
     * 如何分解？
     *
     * 在这里，我们采用递归的方法，首先将待排序列分成A,B两组；然后重复对A、B序列 分组；直到分组后组内只有一个元素，
     * 此时我们认为组内所有元素有序，则分组结束。
     * @param args
     */
    public static void main(String[] args) {
        int[] arry = {5,9,3,4,79,46,89,26,75,8,7,1,55,234,567,234,67,78,34,32};
        //int[] arry = {3,7,6,2,1};
        System.out.println("初始："+Arrays.toString(arry));
        mergeSort(arry);
    }

    /**
     * 归并排序（递归）
     *
     * ①. 将序列每相邻两个数字进行归并操作，形成 floor(n/2)个序列，排序后每个序列包含两个元素；
     * ②. 将上述序列再次归并，形成 floor(n/4)个序列，每个序列包含四个元素；
     * ③. 重复步骤②，直到所有元素排序完毕。
     * @param arry    待排序数组
     */
    public static int[] mergeSort(int[] arry){
        if (arry.length <=1) return arry;
        int half = arry.length >> 1;
        int[] leftArry = Arrays.copyOfRange(arry,0,half);
        int[] rigthArry = Arrays.copyOfRange(arry,half,arry.length);
        System.out.println("split two array: " + Arrays.toString(leftArry) + " And " + Arrays.toString(rigthArry));
        return sort(mergeSort(leftArry),mergeSort(rigthArry));
    }

    public static int[] sort(int[] leftArry,int[] rigthArry){
        int i = 0,j = 0, k = 0;
        int[] result = new int[leftArry.length+rigthArry.length];
        while (i < leftArry.length && j < rigthArry.length){
            if (leftArry[i] < rigthArry[j]){
                result[k++] = leftArry[i++];
            } else{
                result[k++] = rigthArry[j++];
            }
        }
        while (i < leftArry.length){
            result[k++] = leftArry[i++];
        }
        while (j < rigthArry.length){
            result[k++] = rigthArry[j++];
        }
        System.out.println(Arrays.toString(result));
        return result;
    }
}
